Thực đơn
Bộ_lọc_Bloom Xác suất dương tính saiGiả sử các hàm băm lựa chọn các vị trí trong bảng với xác suất như nhau và hoàn toàn ngẫu nhiên và độc lập. Nếu m là số bit trong mảng thì xác suất một bit không được gán giá trị 1 khi ta băm một phần tử bằng một hàm băm là
1 − 1 m . {\displaystyle 1-{\frac {1}{m}}.}Xác suất nó không được gán giá trị 1 bởi bất kì hàm băm nào là
( 1 − 1 m ) k . {\displaystyle \left(1-{\frac {1}{m}}\right)^{k}.}Nếu chèn n phần tử, thì xác suất bit đó vẫn bằng 0 là
( 1 − 1 m ) k n ; {\displaystyle \left(1-{\frac {1}{m}}\right)^{kn};}nên xác suất nó bằng 1 là
1 − ( 1 − 1 m ) k n . {\displaystyle 1-\left(1-{\frac {1}{m}}\right)^{kn}.}Ta xét quá trình kiểm tra liệu một phần tử có nằm trong tập hay không. Thuật toán kiểm tra k vị trí trong mảng xem chúng có bằng 1 hay không. Xác suất tất cả chúng đều bằng 1 là
( 1 − [ 1 − 1 m ] k n ) k ≈ ( 1 − e − k n / m ) k . {\displaystyle \left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}.}Chứng minh này không toàn toàn đúng do nó giả sử xác suất mỗi bit trong mảng được gán giá trị 1 là độc lập với nhau. Tuy nhiên, giả sử đây là một xấp xỉ tốt, thì giá trị k {\displaystyle k} tối ưu để xác suất trên là nhỏ nhất là
m n ln 2 ≈ 0.7 m n , {\displaystyle {\frac {m}{n}}\ln 2\approx 0.7{\frac {m}{n}},}cho giá trị xác suất dương tính sai là
2 − k ≈ 0.6185 m / n . {\displaystyle 2^{-k}\approx {0.6185}^{m/n}.}Có thể tính kích thước m {\displaystyle m} của mảng theo số phần tử n {\displaystyle n} và xác suất dương tính sai p {\displaystyle p} bằng cách thay giá trị tối ưu của k {\displaystyle k} vào biểu thức trên:
p = ( 1 − e − ( m / n ln 2 ) n / m ) ( m / n ln 2 ) {\displaystyle p=\left(1-e^{-(m/n\ln 2)n/m}\right)^{(m/n\ln 2)}}Đơn giản hóa biểu thức trên, ta thu được:
ln p = − m n ( ln 2 ) 2 . {\displaystyle \ln p=-{\frac {m}{n}}\left(\ln 2\right)^{2}.}từ đó thu được:
m = − n ln p ( ln 2 ) 2 . {\displaystyle m=-{\frac {n\ln p}{(\ln 2)^{2}}}.}Nghĩa là để xác suất sai là hằng số cố định, kích thước của mảng là tuyến tính với số phần tử của tập hợp.
Thực đơn
Bộ_lọc_Bloom Xác suất dương tính saiLiên quan
Bộ lọc HEPA Bộ lọc Kalman Bộ lọc Bloom Bộ lọc độ đen trung tính Bộ lọc thông dải Bộ lọc cơ học Bộ lọc cấm dải Bộ luật Hồng Đức Bộ Lao động – Thương binh và Xã hội (Việt Nam) Bộ luật Dân sự PhápTài liệu tham khảo
WikiPedia: Bộ_lọc_Bloom http://webdocs.cs.ualberta.ca/~drafiei/papers/DupD... http://labs.google.com/papers/bigtable.html http://www.deutsche-telekom-laboratories.de/~agarw... http://algo2.iti.uni-karlsruhe.de/singler/publicat... http://www.it-c.dk/people/pagh/papers/bloom.pdf http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa0... http://www.eecs.harvard.edu/~michaelm/postscripts/... http://www.ccs.neu.edu/home/pete/research/bloom-fi... http://www.ccs.neu.edu/home/pete/research/spin-3sp... http://citeseerx.ist.psu.edu/viewdoc/summary?doi=1...